/*
 * bipartite_match.h
 *
 * Copyright (c) 2015-2022, PostgreSQL Global Development Group
 *
 * src/include/lib/bipartite_match.h
 */
#ifndef BIPARTITE_MATCH_H
#define BIPARTITE_MATCH_H

/*
 * 给定一个由编号为 1..nU 的节点 U 和编号为 1..nV 的节点 V 组成的二分图，
 * 以及以形式 adjacency[u] = [k, v1, v2, v3, ... vk] 表示的无向边的邻接图，我们
 * 希望找到一个“最大基数匹配”，定义如下：匹配是原始边的一个子集，且没有节点
 * 具有超过一条边，若存在其他匹配含有更多边，则该匹配具有最大基数。
 *
 * 该匹配在图论中有多种应用，但这里的动机示例是 Dilworth 定理：一个偏序集可
 * 以通过二分图构造拆分为最小数量的链（即子集 X，其中 x1 < x2 < x3 ...）。
 * 这为以可证明的最小排序操作数量规划一组分组集合的问题提供了多项式时间解。
 */
typedef struct BipartiteMatchState
{
	/* inputs: */
	int			u_size;			/* U 的大小 */
	int			v_size;			/* V 的大小 */
	short	  **adjacency;		/* adjacency[u] = [k, v1,v2,v3,...,vk] */
	/* outputs: */
	int			matching;		/* 匹配中的边数量 */
	short	   *pair_uv;		/* pair_uv[u] -> v */
	short	   *pair_vu;		/* pair_vu[v] -> u */
	/* 匹配算法的私有状态： */
	short	   *distance;		/* distance[u] */
	short	   *queue;			/* 广度搜索的队列存储 */
} BipartiteMatchState;

extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);

extern void BipartiteMatchFree(BipartiteMatchState *state);

#endif							/* BIPARTITE_MATCH_H */
